#coding=utf-8

# poke = [[7,3],[7,2],[13,3],[13,3],[8,2]]
# dp = [1 for i in range(len(poke))]
#
# def is_compile(x,y):
#     if x[0] == y[0]: return True
#     elif x[1] == y[1]: return True
#     elif x[0] == 8 or y[0] == 8: return True
#     else: return False
#
# for i in range(len(poke)):
#     for j in range(i):
#         if is_compile(poke[i],poke[j]):
#             dp[i] = max(dp[j]+1,dp[i])
# print(dp)


#背包问题

n = int(input("请输入物品的数量: "))
w = []
v = []
for i in range(1,n+1):
    x , y = map(int,input(f"请输入第{i}个物品的重量和价值: ").split())
    w.append(x)
    v.append(y)
def cal_v(s1:list)->int:
    sum = 0
    for i,j in zip(s1,v):
        sum += i*j
    return sum
maxwight = int(input("请输入最大重量: "))
dp = [[{i:[0]*n} for i in range(maxwight+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,maxwight+1):
        if j < w[i - 1]:  # 如果剩余容量不够新来的物体 直接等于之前的
            dp[i][j] = dp[i - 1][j]
        else:
            sum1 = cal_v(dp[i - 1][j][j])
            sum2 = cal_v(dp[i - 1][j - w[i - 1]][j - w[i - 1]]) + v[i - 1]
            if sum1 >= sum2:
                dp[i][j][j] = dp[i - 1][j][j]
            else:
                dp[i][j][j] = dp[i - 1][j - w[i - 1]][j - w[i - 1]]
                dp[i][j][j][i-1] = 1
print(*dp[-1][-1][maxwight])



